package Algorithm.DynamicPlanning;

public class Code07_SnakeGame {

    public static int walk1(int[][] matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++){
                int[] ans = process(matrix, i, j);
                res = Math.max(res, Math.max(ans[0], ans[1]));
            }
        }
        return res;
    }

    // 从左侧到达(i,j)的旅程中
    // 0) 在没有使用过能力的情况下，返回路径最大和
    // 1) 在使用过能力的情况下，返回路径最大和
    public static int[] process(int[][] m, int i, int j){
        if (j == 0){ // (i,j)就是最左侧的位置
            return new int[] {m[i][0], -m[i][0]};
        }
        // 第一条路(左侧)
        int[] preAns = process(m, i, j - 1);
        // preUnuse  之前旅程，没用过能力
        // preUse    之前旅程，已经使用过能力了
        int preUnuse = preAns[0];
        int preUse = preAns[1];
        if (i - 1 >= 0){ // 左上
            preAns = process(m, i - 1, j - 1);
            preUnuse = Math.max(preUnuse, preAns[0]);
            preUse = Math.max(preUse, preAns[1]);
        }
        if (i + 1 < m.length){ // 左下
            preAns = process(m, i + 1, j - 1);
            preUnuse = Math.max(preUnuse, preAns[0]);
            preUse = Math.max(preUse, preAns[1]);
        }
        // 之前没使用过能力，当前位置也不使用能力，的最优解
        int no = -1;
        // 不管是之前使用能力，还是当前使用了能力，请保证能力只使用一次，最优解
        int yes = -1;
        if (preUnuse >= 0){
            no = preUnuse + m[i][j];
            yes = preUnuse - m[i][j];
        }
        if (preUse >= 0){ // 之前使用了
            // no = preUnuse + m[i][j];
            yes = Math.max(yes, preUse + m[i][j]);
        }
        return new int[] {no, yes};
    }
    // 改动态规划
    public static int walk2(int[][] matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int[][][] dp = new int[matrix.length][matrix[0].length][2];
        for (int i = 0; i < matrix.length; i++) { // 第0列赋值
            dp[i][0][0] = matrix[i][0];
            dp[i][0][1] = -matrix[i][0];
            max = Math.max(dp[i][0][0], dp[i][0][1]);
        }

        for (int j = 1; j < matrix[0].length; j++){
            for (int i = 0; i < matrix.length; i++) {
                int preUnuse = dp[i][j - 1][0]; // 先赋值左边的
                int preUse = dp[i][j - 1][1];
                if (i - 1 >= 0){ // 左上
                    preUnuse = Math.max(preUnuse, dp[i - 1][j - 1][0]);
                    preUse = Math.max(preUse, dp[i - 1][j - 1][1]);
                }
                if (i + 1 < matrix.length){ // 左下
                    preUnuse = Math.max(preUnuse, dp[i + 1][j - 1][0]);
                    preUse = Math.max(preUse, dp[i + 1][j - 1][1]);
                }
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
                if (preUnuse >= 0){
                    dp[i][j][0] = preUnuse + matrix[i][j];
                    dp[i][j][1] = preUnuse - matrix[i][j];
                }
                if (preUse >= 0){
                    dp[i][j][1] = Math.max(dp[i][j][1], preUse + matrix[i][j]);
                }
                max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                { -100, -4000, -10000 },
                { -200, -2000, -100000 },
                { -300, -1000, -60000 },
                { -2000, -5000, -20000000 } };
        System.out.println(walk1(matrix));
        System.out.println(walk2(matrix));
    }
}
